package leetcode_900;

/**
 *@author 周杨
 *MinimumSwapsToMakeSequencesIncreasing_801_ 同一个index可以互换元素 要保证两个数组都严格递增 那么互换多少次最小合法
 *describe:用动态规划 AC 36%
 *2018年10月24日 下午12:31:21
 */
public class MinimumSwapsToMakeSequencesIncreasing_801_ {
	public static void main(String[] args) {
		MinimumSwapsToMakeSequencesIncreasing_801_ test=new MinimumSwapsToMakeSequencesIncreasing_801_();
		//System.out.println(test.minSwap(new int[] {1,3,5,4}, new int[]{1,2,3,7}));
		//System.out.println(test.minSwap(new int[] {0,3,5,8,9}, new int[]{2,1,4,6,9}));
		System.out.println(test.minSwap(new int[] {0,1,4,6,8}, new int[]{1,2,2,7,10}));
	}
	
	public int minSwap(int[] A, int[] B) {
        int reverse=1,noreverse=0;
        for(int i=1;i<A.length;++i) {
        	int temR=reverse,temN=noreverse;
        	if(A[i]>A[i-1]&&B[i]>B[i-1]) {//不用反转就合法
        		temR=reverse+1;//那么双反转也合法
        		if(B[i]>A[i-1]&&A[i]>B[i-1]) {//反转也合法
        			temR=Math.min(noreverse+1, temR);
        			temN=Math.min(noreverse, reverse);
        		}
        	}
        	else {//必须反转 双反转已经走过了
        		temR=noreverse+1;
        		temN=reverse;
        	}
        	reverse=temR;
        	noreverse=temN;
        }
        return Math.min(reverse, noreverse);
    }
}
